package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/">在排序数组中查找元素的第一个和最后一个位置(Find First and Last Position of Element in Sorted Array)</a>
 * <p>给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。</p>
 * <p>如果数组中不存在目标值 target，返回 [-1, -1]。</p>
 * <p>你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [5,7,7,8,8,10], target = 8
 *      输出：[3,4]
 *
 * 示例 2：
 *      输入：nums = [5,7,7,8,8,10], target = 6
 *      输出：[-1,-1]
 *
 * 示例 3：
 *      输入：nums = [], target = 0
 *      输出：[-1,-1]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>0 <= nums.length <= 10^5</li>
 *      <li>-10^9 <= nums[i] <= 10^9</li>
 *      <li>nums 是一个非递减数组</li>
 *      <li>-10^9 <= target <= 10^9</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/19 15:13
 */
public class LC0034FindFirstAndLastPositionOfElementInSortedArray_M {

    static class Solution {
        /**
         * 目标值在数组中的开始和结束位置，其实要找的就是数组中「第一个等于 target 的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）。
         */
        public int[] searchRange(int[] nums, int target) {
            // 找到target的最左索引位置
            int start = binarySearch(nums, target);
            // target不存在于数组中
            if (start == nums.length || nums[start] != target) {
                return new int[]{-1, -1};
            }
            // start存在，end必定存在
            // 找到target+1的最左索引位置，减1即为target的最右索引位置
            int end = binarySearch(nums, target + 1) - 1;
            return new int[]{start, end};
        }

        public int[] searchRange2(int[] nums, int target) {
            if (nums == null || nums.length == 0) {
                return new int[]{-1, -1};
            }
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] < target) {
                    left = mid + 1;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid - 1;
                    right = mid + 1;
                    while (left >= 0 && nums[left] == target) {
                        --left;
                    }
                    while (right <= nums.length - 1 && nums[right] == target) {
                        ++right;
                    }
                    return new int[]{left + 1, right - 1};
                }
            }
            return new int[]{-1, -1};
        }

        private int binarySearch(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (nums[mid] >= target) {
                    right = mid - 1;    // 范围缩小到 [left, mid - 1]
                } else {
                    left = mid + 1;     // 范围缩小到 [mid + 1, right]
                }
            }
            return left;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8));
        Printer.printArrayInt(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6));
        Printer.printArrayInt(solution.searchRange(new int[]{1, 1, 2}, 1));
        Printer.printArrayInt(solution.searchRange(new int[]{}, 0));
    }
}